import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class Leetcode17 {

    private final static List<List<Character>> strArray = Arrays.asList(
            List.of(),
            Arrays.asList('a', 'b', 'c'),
            Arrays.asList('d', 'e', 'f'),
            Arrays.asList('g', 'h', 'i'),
            Arrays.asList('j', 'k', 'l'),
            Arrays.asList('m', 'n', 'o'),
            Arrays.asList('p', 'q', 'r', 's'),
            Arrays.asList('t', 'u', 'v'),
            Arrays.asList('w', 'x', 'y', 'z')
    );

    public List<String> letterCombinations(String digits) {
        char[] numbers = digits.toCharArray();
        List<List<Character>> c = new ArrayList<>();
        for (char number : numbers) {
            c.add(strArray.get(number - '1'));
        }

        if (c.size() == 0) {
            return List.of();
        }
        List<String> res = new ArrayList<>();
        for (Character character : c.get(0)) {
            res.add(String.valueOf(character));
        }

        List<String> existRes;
        for (int i = 1; i < c.size(); i++) {
            existRes = new ArrayList<>();
            for (int j = 0; j < res.size(); j++) {
                for (int k = 0; k < c.get(i).size(); k++) {
                    existRes.add(res.get(j) + c.get(i).get(k));
                }
            }
            res = existRes;
        }

        return res;
    }
}
